Sorting by transposition

The simplest sorting algorithms use transposition to sort an array of data. Three major algorithms in this type are insertion sort, bubble sort, selection sort. I also write about heapsort that is an algothm that apply the principle behind the selection sort more efficiently. I will show sample implementations of these algorithms and then analyze the performances.

Insertion sort

An intuitive way for humans to sort things is to pick two things and put them in order, and then pick next to put it in the correct position, and so on. This also can be done on the computer, and the algorithm is called insertion sort.

In [1]:

object InsertionSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    for (i <- 1 until array.length) {
      var j = i - 1
      val value = array(j + 1)
      while (j >= 0 && ordering.compare(value, array(j)) < 0) {
        array(j + 1) = array(j)
        j -= 1
      }
      array(j + 1) = value
    }
  }
}

Out[1]:

defined object InsertionSort

Bubble Sort

This algorithm have no intuitive interpretation and is the slowest of all the major sorting algorithms. However, it is important because the principle can be refined to be more effcient.

In [2]:

object BubbleSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    for (i <- 0 to array.length - 2)
      for (j <- array.length - 1 until i by -1)
        if (ordering.compare(array(j), array(j - 1)) < 0) {
          val temp = array(j - 1)
          array(j - 1) = array(j)
          array(j) = temp
        }
  }
}

Out[2]:

defined object BubbleSort

Selection Sort

Bubble sort is slow particularly because it has to repeatedly swap adjacent element from bottom to the top to put the (next) smallest element into the correct position. Instead, selection sort remembers the position of the smallest element when it searches through the array, and swap element only one time for each next smallest element.

In [3]:

object SelectionSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    for (i <- 0 to array.length - 2) {
      var minIndex = i
      for (j <- array.length - 1 until i by -1)
        if (ordering.compare(array(j), array(minIndex)) < 0) minIndex = j
      val temp = array(minIndex)
      array(minIndex) = array(i)
      array(i) = temp
    }
  }
}

Out[3]:

defined object SelectionSort

Heapsort

Like selection sort, heapsort find the maximum value in the array. However, using the data structure called heap, it doesn't need to do $n-i$ comparison to find ith largest element.

In [4]:

object HeapSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    buildHeap(array)
    for (i <- array.length - 1 to 1 by -1) {
      val temp = array(0)
      array(0) = array(i)
      array(i) = temp
      heapify(array, 0, i)
    }
  }

  def buildHeap[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    for (i <- array.length / 2 - 1 to 0 by -1)
      heapify(array, i, array.length)
  }

  def heapify[T](array: Array[T], index: Int, maxIndex: Int)
                (implicit ordering: Ordering[T]): Unit = {
    var largestIndex = index
    var leftIndex = 2 * index + 1
    var rightIndex = 2 * index + 2

    if (leftIndex < maxIndex
      && ordering.compare(array(leftIndex), array(largestIndex)) > 0)
      largestIndex = leftIndex
    if (rightIndex < maxIndex
      && ordering.compare(array(rightIndex), array(largestIndex)) > 0)
      largestIndex = rightIndex
    if (largestIndex != index) {
      val temp = array(index)
      array(index) = array(largestIndex)
      array(largestIndex) = temp
      heapify(array, largestIndex, maxIndex)
    }
  }
}

Out[4]:

defined object HeapSort

Comparison of the algorithms

For the extra space used in sorting, all of these algorithms need only constant space. The former three algorithms run in $\Theta(n^2)$ time for average and worst cases. However, they behave differently in the best case. Insertion sort runs in $\Theta(n)$ time while the others in $\Theta(n^2)$ time. Since selection sort is the obvious improvement from bubble sort, selection sort runs faster than bubble sort by constant factor. Heapsort runs in $\Theta(n\log n)$ time in best, average, worst cases.

Practical use cases

These algorithms are not particularly fast in the average (expected) cases. However, because of the favorable near best case behaviour of the insertion sort, when you know in advance that the array is mostly sorted, insertion sort runs the fastest. Other than that, insertion sort is used when the array is short. For the charasteristics, insertion sort is often used to be combined with other sophisticated sorting algorithms. Heapsort runs relatively fast and has good worst case time complexity so that it is used when worst case behaivour is concerned.

Yuta Nishino